#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

void HeapInit(Heap* php)
{
	assert(php);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

void Swap(int* x, int* y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

void AdjustUp(int* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	
	while (child > 0)
	{
		//大堆         >
	    //小堆         <
		if (arr[child] > arr[parent])//big
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* php, int x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		int* tmp = (int*)realloc(php->arr, sizeof(int) * newCapacity);
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	AdjustUp(php->arr,php->size);
	php->size++;
}

void AdjustDown(int* arr, int parent, int n)
{
	assert(arr);
	int child = parent * 2 + 1;
	
	while (child < n)
	{
        //大堆                          <
        //小堆                          >
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child = child + 1;
		}
		//大堆         >
		//小堆         <
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* php)
{
	assert(!HeapEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;

	AdjustDown(php->arr, 0, php->size);
}

int HeapTop(Heap* php)
{
	assert(!HeapEmpty(php));
	return php->arr[0];
}

void HeapPrint(Heap* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}

void BubbleSort(int* arr,int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
				flag = 0;
			}
		}
		if (flag)
			break;
	}
}

void HeapSort(int* arr, int n)
{
	assert(arr);
	//升序->建大堆
	//降序->建小堆

	//向下调整建堆
	for ( int i = (n-1-1)/2; i >=0 ; i--)
	{
		AdjustDown(arr, i, n);
	}
	//向上调整建堆
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/

	int ct = n - 1;
	while ( ct > 0 )
	{
		Swap(&arr[0], &arr[ct]);
		AdjustDown(arr, 0, ct);
		ct--;
	}
}

int Heapsize(Heap* php)
{
	assert(php);
	return php->size;
}